Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Simplify Path

Problem Statement

Given an absolute file path in a Unix-style file system, simplify it by converting ".." to the previous directory and removing any "." or multiple slashes. The resulting string should represent the shortest absolute path.

Examples

Example 1

  • Input: path = "/a//b////c/d//././/.."
  • Expected Output: "/a/b/c"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • "." refers to the current directory and is ignored.
    • ".." moves up one directory, so "d" is removed.
    • The simplified path is "/a/b/c".

Example 2

  • Input: path = "/../"
  • Expected Output: "/"
  • Explanation:
    • ".." moves up one directory, but we are already at the root ("/"), so nothing happens.
    • The final simplified path remains "/".

Example 3

  • Input: path = "/home//foo/"
  • Expected Output: "/home/foo"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • The final simplified path is "/home/foo".

Constraints:

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.

Solution

To simplify the path, we'll use a stack to track the directories we're currently in. We'll split the input path into components by the "/" character, then process each component one by one. If a component is "..", we go to the previous directory by popping the top of the stack. If a component is "." or an empty string, we do nothing. Otherwise, we push the component into the stack as a new directory.

Step-by-Step Algorithm

  1. Split the input path by the "/" character into an array of components.

  2. Initialize an empty stack.

  3. For each component in the array:

    • If the component is "..", pop the top of the stack (if it's not already empty).
    • Else if the component is "." or an empty string, do nothing.
    • Else, push the component into the stack as a new directory.
  4. Merge all elements in the stack into a string by reversing the order and joining them with the '/' character. Ensure the final path starts with '/' to represent an absolute path.

Algorithm walkthrough

Image
  1. Initialize a Stack: A Stack<String> is created to store components of the simplified path.

  2. Split the Path: The input path "/a//b////c/d//././/.." is split using "/" as the delimiter. The resulting parts are: ["", "a", "", "b", "", "", "", "c", "d", "", ".", "", ".", "", "", ".."]. Empty strings and dots (".") represent the current directory and will be ignored in further processing.

  3. Process Each Part:

    • First Part (""): It's empty, so it's ignored.
    • Second Part ("a"): It's a directory name and is pushed onto the stack.
    • Third Part (""): Ignored.
    • Fourth Part ("b"): Another directory name, pushed onto the stack.
    • Next Several Parts ("", "", ""): All empty, so ignored.
    • Part "c": A directory name, pushed onto the stack.
    • Part "d": Another directory name, pushed onto the stack.
    • Part ".": Represents the current directory, ignored.
    • Part "." (again): Again, represents the current directory, ignored.
    • Last Part (".."): Represents moving up one directory. It pops "d" from the stack.

    After processing, the stack contains: ["a", "b", "c"].

  4. Reconstruct Simplified Path: Next, create the resulting string by joining all stack elements with the '/' character in reverse order.

    • After processing the stack, the string contains "/a/b/c".
  5. Return the Result:

    • For the given input, the output is "/a/b/c".

Code

Here is the code for this algorithm:

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Splitting the path: The input string path is split using / as the delimiter, which takes time, where N is the length of the input string path. This creates an array of strings representing the components of the path.

  • Processing the components: The algorithm processes each component of the path array. For each component, it either pushes it onto the stack, pops an element from the stack, or skips the component if it is . or empty. Since each component is processed at most once, this takes time in total.

  • Building the result: After processing all components, the algorithm reconstructs the simplified path by concatenating the elements in the stack. This also takes time.

Overall time complexity: , where N is the length of the input string path.

Space Complexity

  • Stack space: The stack stores the components of the simplified path. In the worst case, the stack contains all components of the path, which requires space.

  • Result string space: The result string is used to store the final result which also takes space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: .

Simplify Path (medium)
Lowest Common Ancestor of a Binary Search Tree (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity